/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  /*
  // 递归
  TreeNode* pre;
  bool isValidBST(TreeNode* root) {
      if(!root) return true;
      bool left = isValidBST(root->left);
      if(pre && root->val <= pre->val) {
          return false;
      }
      pre = root;
      bool right = isValidBST(root->right);
      return left&&right;
  }
  */
  // 迭代,中序
  bool isValidBST(TreeNode* root) {
    stack<TreeNode*> st;
    TreeNode* cur = root;
    TreeNode* pre = NULL;  // 记录前一个节点
    while (cur != NULL || !st.empty()) {
      if (cur != NULL) {
        st.push(cur);
        cur = cur->left;  // 左
      } else {
        cur = st.top();  // 中
        st.pop();

        if (pre != NULL && cur->val <= pre->val) return false;
        pre = cur;  //保存前一个访问的结点

        cur = cur->right;  // 右
      }
    }
    return true;
  }
};
/*
// 注意二叉搜索树中不能有重复元素。中序遍历序列是一个递增序列
class Solution {
private:
    vector<int> vec;
    void traversal(TreeNode* root) {
        if (root == NULL) return;
        traversal(root->left);
        vec.push_back(root->val); // 将二叉搜索树转换为有序数组
        traversal(root->right);
    }
public:
    bool isValidBST(TreeNode* root) {
        vec.clear(); // 不加这句在leetcode上也可以过，但最好加上
        traversal(root);
        for (int i = 1; i < vec.size(); i++) {
            // 注意要小于等于，搜索树里不能有相同元素
            if (vec[i] <= vec[i - 1]) return false;
        }
        return true;
    }
};

*/
// TODO: 中序遍历 的 迭代版本怎么写?
// https://www.programmercarl.com/0098.%E9%AA%8C%E8%AF%81%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E9%80%92%E5%BD%92%E6%B3%95